package com.skh.array;

/**
 * 将每个元素替换为右侧最大元素
 */
public class ReplaceElements {

    /**
     * 给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
     *
     * 完成所有替换操作后，请你返回这个数组。
     *
     * 示例：
     *
     * 输入：arr = [17,18,5,4,6,1]
     * 输出：[18,6,6,6,1,-1]
     *  
     * 提示：
     *
     * 1 <= arr.length <= 10^4
     * 1 <= arr[i] <= 10^5
     */

    /**
     * 思路:暴力枚举
     * @param arr
     * @return
     */
    public int[] replaceElements(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int max = 1;

            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] > max) {
                    max = arr[j];
                }
            }
            arr[i] = max;
        }

        arr[arr.length-1] = -1;
        return arr;
    }


    /**
     * 思路:逆序遍历,寻找最大值
     * @param arr
     * @return
     */
    public int[] replaceElements1(int[] arr) {
        int max = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            int curMax = arr[i];
            arr[i] = max;
            if (curMax > max) {
                max = curMax;
            }
        }
        return arr;
    }
}
